Die Untersuchungen des Arbeitsbereiches sind im Bereich der Formalen Sprachen und der Komplexitätstheorie angesiedelt. Zentraler Forschungsaspekt ist hierbei die Behandlung paralleler Berechnungen.
Der Arbeitsbereich wurde neu eingerichtet und hat seine Arbeiten am 1. Oktober 1994 aufgenommen. Die unter Forschungs- und Entwicklungsprojekte angeführten Forschungsvorhaben basieren weitgehend auf Vorarbeiten, die an der Universität Stuttgart und an der Technischen Universität München erbracht wurden. Es werden nicht nur abgeschlossene Arbeiten dargestellt, sondern auch Fragestellungen, die gegenwärtig am Arbeitsbereich Theoretische Informatik/Formale Sprachen behandelt werden.
(C. Damm (Universität Trier),
M. Holzer)
Es wurde eine neues nichtuniformes Berechnungsmodell, die
sogenannte programmierte Turingmaschine, eingeführt. Im Falle
eines Speicherplatzbedarfes von O(log n) stimmt das nichtuniforme
Modell der programmierten Turingmaschine mit dem
Nichtuniformitätsbegriff von Karp und Lipton überein. Es
konnte die Äquivalenz platzbeschränkter programmierter
Turingmaschinen und Verzweigungsprogrammen mit beschränkter
Weite gezeigt werden. Darüberhinaus wurde gezeigt, daß
nichtuniforme nichtdeterministische Klassen mit o(log n)
Speicherplatz unter Komplement abgeschlossen sind. Zum Beweis
wurde die Technik des induktiven Zählens auf
Verzweigungsprogramme übertragen. Die Ergebnisse
wurden auf der 19ten Konferenz Mathematical Foundations of
Computer Science präsentiert.
(C. Damm
(Universität Trier),
M. Holzer)
Der Nichtuniformitätsbegriff von Karp und Lipton wurde in
Zusammenhang mit Automatenmodellen für formalsprachliche
Klassen studiert. Dabei konnte eine vollständige Separierung
für die Nichtuniformen Klassen der Chomsky-Hierarchie
gefunden werden. Darüberhinaus konnten Bezüge zu anderen
aus der Literatur bekannten Nichtuniformitätsmaßen
aufgezeigt werden.
Diekert (Universität Stuttgart), Muscholl (Universität Stuttgart), Reinhardt
Die Spurtheorie hat sich als geeigneter Rahmen für die Untersuchung paralleler Systeme erwiesen. Das Konzept der Spuren formalisiert auf einfache Art den Kern eines nebenläufigen Systems in Form einer Menge atomarer Aktionen. Die Verfeinerung von Aktionen kann dabei durch einen Morhpismus beschrieben werden. Soll die Verfeinerung auch rückgängig zu machen sein, so muß der Morhismus eine Kodierung sein.
Daher beschreiben wir für gegebene Spurmonoide Kriterien für die Existenz einer Kodierung.
Kunde (TU München), R. Niedermeier, K. Reinhardt, Rossmanith (TU München)
Es wurde das Durchschnittsfallverhalten für das Sortierproblem bei gitterartig verbundenen Prozessornetzwerken (konventionelle Gitter, Tori, Gitter mit Diagonalen, rekonfigurierbare Gitter) untersucht. Dabei wurde von (der üblichen Annahme) einer Gleichverteilung der Eingabe ausgegangen. Es zeigte sich, daß im Durchschnitt in der Regel doppelt so schnell sortiert werden kann wie im sogenannten Worst Case.
Der Sortieralgorithmus für Sortieren im Durchschnitt basiert grundlegend auf dem von Manfred Kunde vorgestellten Verfahren (European Symposium on Algorithms 1993) des Sortierens mit `Äll-to-all Mappings'". Die entscheidene Beobachtung ist, das fuer den Durchschnittsfall eine statt zwei All-to-all Mappings (die die Komplexität des Gesamtalgorithmus dominiert) genügt, um mit einer exponentiell nahe bei~1 gelegenen Wahrscheinlichkeit ein korrekt sortiertes Ergebnis zu erzielen. Da wir auch untere Schranken angeben konnten, die sich asymptotisch mit den oberen Schranken decken, folgt, daß unsere Ergebnisse optimal sind.
Für die Analyse unseres Algorithmus benutzten wir unter anderem Chernoff Schranken. Es wurde gegenüber bisher bekannten Ergebnissen zu diesem Bereich (die z. T. auch deutlich verbessert wurden) auch eine andere Modellierung angegeben und eine neuartige Analyse bis ins Detail durchgeführt. Neben der Verallgemeinerung bisheriger Ergebnisse konnte mit dieser Arbeit auch eine Widerlegung einer Vermutung von Gu und Gu (IEEE Transactions on Parallel and Distributed Systems, März 1994) bezueglich des Sortierens auf Tori erreicht werden.
Da mit Sortieren auch das Routing-Problem gelöst werden kann, impliziert unser Ergebnis auch optimale Routing-Verfahren für gitterförmig verbundene Prozessornetzwerke.
K.-J. Lange, R. Niedermeier, K. Reinhardt
Nachdem schon die komplexitätstheoretische Klassifizierung von Kommunikationsstrukturen paralleler Algorithmen erfolgreich betrieben wurde, wird nun angestrebt, auch eine komplexitätstheoretische Klassifizierung des Synchronisationsbedarfs paralleler Algorithmen zu finden. Die Frage ist, ob eine Charakterisierung mit bekannten Konzepten der Komplexitätstheorie möglich ist und welche Rückschlüsse aus etwaigen Charakterisierungen für die Beurteilung vorhandener paralleler Algorithmen zu ziehen sind.
K.-J. Lange, K. Reinhardt
Bei der leeren Alternierung wird das bekannte Prinzip der Alternierung dadurch eingeschränkt, daß der Keller bzw. ein nicht logarithmisch platzbeschränktes Band beim Alternieren leer sein muß. Damit erhalten wir folgende Ergebnisse:
Mit einer leer alternierenden polynomiell zeitbeschränkten Turingmaschine wird die Orakelkomlexitätsklasse $\Theta_2^p:=L^{NP}$ charakterisiert. (Volle Alternierung erreicht hier $PSPACE$.)
Mit einem leer alternierenden polynomiell zeitbeschränkten Kellerautomat mit logarithmisch platzbeschränktem Band wird bei beliebiger Alternierung $P$, bei konstanter Alternierung $LOGCFL$ und bei $log^k$ Alternierung die Schaltkreiskomplexitätsklasse $AC^k$ charakterisiert. (Volle Alternierung erreicht bei konstanter Alternierung Stufen der polynomiellen Hierarchie und bei beliebiger Alternierung $PSPACE$.)
R. Niedermeier, Rossmanith (TU München)
Auf der Suche nach dem "richtigen" Modell für die komplexitätstheoretische Behandlung paralleler Algorithmen gibt es die Extreme einerseits der synchronen PRAM (Parallel Random Access Machine) mit keinerlei Unterscheidung zwischen Zugriffen auf den gemeinsamen globalen oder die einzelnen lokalen Speicher und andererseits die Annahme von asynchronen Maschinen mit verteiltem Speicher. Es wird versucht, einen Mittelweg zu finden zwischen den "`realitätsfeindlichen"' Annahmen der PRAM und den "`theoriefeindlichen" Gegebenheiten existierender Parallelrechner, um zwar immer noch theoretisch fundierte, aber praxisrelevantere Aussagen über parallele Algorithmen treffen zu können.
K. Reinhardt
Mit Halbspuren bzw. Halbspursprachen lassen sich mögliche Reihenfolgen der einzelnen Aktionen von Prozessen beschreiben. Eine der dabei auftretende Fragestellungen ist die Synchronisierbarkeit von durch Halbspur(sprach)en beschriebenen Teilprozessen in einem verteilten System.
Es werden notwendige und hinreichende Kriterien für solche Semikommutationssysteme beschrieben, bei denen eine Halbspursprache, d.h. die die Hülle einer regulären Sprache unter diesem Semikommutationssystem, von einem Prioritätsmulticounterautomaten erkannt werden kann. Da das Leerheitsproblem für die von einem Prioritätsmulticounterautomaten erkannte Sprache und damit auch das Halteproblem für Prioritätsmulticounterautomaten entscheidbar ist, kann damit die Maximalität und die Synchronisierbarkeit von Halbspursprachen in diesen Fällen entschieden werden. Allgemein sind diese Fragen jedoch unentscheidbar.
Ferner werden die Beziehungen der von diesen Automaten erkannten Prioritätsmulticountersprachen zu anderen Sprachklassen beschrieben, verschiedene Arten von Zählerautomaten verglichen und dabei u.a. gezeigt, daß die Sprache $\{(a^nb)^m \mid n,m \in \N\}$ keine Prioritätsmulticountersprache ist. In diesem Zusammenhang wurde gezeigt, daß das Erreichbarkeitsproblem für Petrinetze, bei denen die inhibitorischen Kanten auf eine bestimmte Art und Weise angeordnet sind, entscheidbar ist.
This page was last updated on Juli 18th, 1997 by P. Meißner